#define _CRT_SECURE_NO_WARNINGS 2

#include<iostream>
#include<algorithm>

using namespace std;

int tmp[20] = { 0 };

void MergeSort(int arr[], int left, int right)
{
	if (left >= right)	return;
	int mid = (left + right) >> 1;
	MergeSort(arr, left, mid);
	MergeSort(arr, mid + 1, right);
	int cur1 = left, cur2 = mid + 1, i = 0;
	while (cur1 <= mid && cur2 <= right)
	{
		if (arr[cur1] < arr[cur2])	tmp[i++] = arr[cur1++];
		else tmp[i++] = arr[cur2++];
	}
	while(cur1<=mid)		tmp[i++] = arr[cur1++];
	while(cur2<=right)		tmp[i++] = arr[cur2++];

	for (int k = left; k <= right; k++)
	{
		arr[k] = tmp[k - left];
	}
}

void SelectSort(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		int min = arr[i];
		int index = i;
		for (int j = i+1; j < n; j++)
		{
			if (arr[j] < min)
			{
				index = j;
				min = arr[j];
			}
		}
		swap(arr[i], arr[index]);
	}
}

void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
}

int main()
{
	int arr[] = { 4,5,9,-1,9,0 };
	//MergeSort(arr,0,5);
	SelectSort(arr, 6);
	Print(arr, 6);
	return 0;
}